package com.msb.平衡树;

// 40min
// https://leetcode.cn/problems/validate-binary-search-tree/
public class Code05_IsBinarySearchTree {

	public static class TreeNode {
		public int val;
		public TreeNode left;
		public TreeNode right;

		TreeNode(int val) {
			this.val = val;
		}
	}
	
	public static class Info{
		int min;
		int max;
		boolean isSer;

	}

	// 求左右节点的, 最大值最小值, 要保持两边是同等全
	// 空值处理
	// 大坑: right和left的最大最小都需要, 然后不要手滑写错了, 要检查
	public Info check(TreeNode root) {
		if (root == null) {
			return null;
		}
		Info info = new Info();
		Info leftI = check(root.left);
		if (leftI != null && !leftI.isSer) {
			info.isSer = false;
			return info;
		}
		Info rightI = check(root.right);
		if (rightI != null && !rightI.isSer) {
			info.isSer = false;
			return info;
		}
		info.max = leftI == null ? root.val : Math.max(root.val, leftI.max);
		info.max = rightI == null ? info.max : Math.max(info.max, rightI.max);
		info.min = rightI == null ? root.val : Math.min(root.val, rightI.min);
		info.min = leftI == null ? info.min : Math.min(info.min, leftI.min);

		info.isSer = (leftI == null || root.val > leftI.max) && (rightI == null ||root.val < rightI.min);
		return info;
	}

	public boolean isValidBST(TreeNode root) {
		return check(root).isSer;
	}

//	public static void main(String[] args) {
//		TreeNode treeNode = new TreeNode(1);
//		TreeNode treeNode3 = new TreeNode(1);
//		treeNode.left = treeNode3;
//		System.out.println(new Code05_IsBinarySearchTree().isValidBST(treeNode));
//	}
}
